#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
#include <stack>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

class Graph
{
private:
    unordered_map<char, vector<char>> adjacencyList; // 邻接表
    unordered_map<char, int> nodeValues;

public:
    // 添加节点和边
    void addNode(char node, int value)
    {
        nodeValues[node] = value;
    }

    void addEdge(char from, char to)
    {
        adjacencyList[from].push_back(to);
        adjacencyList[to].push_back(from); // 无向图需要双向添加边
    }

    // 绘制邻接矩阵
    void printAdjacencyMatrix()
    {
        for (auto &pair : adjacencyList)
        {
            cout << pair.first << ": ";
            for (char neighbor : pair.second)
            {
                cout << neighbor << " ";
            }
            cout << endl;
        }
    }

    // 统计边的数量并展示所有边
    void printEdges()
    {
        unordered_set<string> edges;
        for (auto &pair : adjacencyList)
        {
            for (char neighbor : pair.second)
            {
                string edge = "(" + string(1, pair.first) + "- " + string(1, neighbor) + ")";
                edges.insert(edge);
            }
        }
        cout << "总的边: " << edges.size() << endl;
        cout << "Edges: ";
        for (const string &edge : edges)
        {
            cout << edge << " ";
        }
        cout << endl;
    }

    // 广度优先遍历
    void BFS(char startNode)
    {
        unordered_set<char> visited;
        queue<char> q;
        q.push(startNode);

        cout << "BFS 遍历, 从" << startNode << " 开始# ";
        while (!q.empty())
        {
            char node = q.front();
            q.pop();
            if (visited.find(node) == visited.end())
            {
                cout <<"("<< node <<" "<<nodeValues[node] <<" )->";
                visited.insert(node);
                for (char neighbor : adjacencyList[node])
                {
                    if (visited.find(neighbor) == visited.end())
                    {
                        q.push(neighbor);
                    }
                }
            }
        }
        cout << endl;
    }

    // 广度优先搜索某个节点
    void breadthFirstSearch(char startNode, char targetNode)
    {
        unordered_set<char> visited;
        queue<char> q;
        q.push(startNode);

        cout << "BFS 搜索" << startNode << " -> " << targetNode << ": ";
        while (!q.empty())
        {
            char node = q.front();
            q.pop();
            if (node == targetNode)
            {
                cout << node << " ---------target val#";

                cout << nodeValues[node] << " "; // 输出节点的值
                cout << endl;
                break;
            }
            if (visited.find(node) == visited.end())
            {
                cout << node << " ";
                visited.insert(node);
                for (char neighbor : adjacencyList[node])
                {
                    if (visited.find(neighbor) == visited.end())
                    {
                        q.push(neighbor);
                    }
                }
            }
        }
    }

    void DFS(char startNode)
    {
        unordered_set<char> visited;
        stack<char> s;
        s.push(startNode);

        cout << "DFS 遍历, 从" << startNode << " 开始# ";
        while (!s.empty())
        {
            char node = s.top();
            s.pop();
            if (visited.find(node) == visited.end())
            {
                cout << node << " ";
                visited.insert(node);
                for (char neighbor : adjacencyList[node])
                {
                    if (visited.find(neighbor) == visited.end())
                    {
                        s.push(neighbor);
                    }
                }
            }
        }
        cout << endl;
    }

    // 深度优先搜索
    bool DFSSearch(char currentNode, char targetNode, unordered_set<char> &visited, vector<char> &path)
    {
        visited.insert(currentNode);
        path.push_back(currentNode);

        if (currentNode == targetNode)
        {
            // cout << "Path found: ";
            for (char node : path)
            {
                cout << node << " ";
            }

            cout << "-------target val#" << nodeValues[targetNode] << " ";
            cout << endl;
            return true;
        }

        for (char neighbor : adjacencyList[currentNode])
        {
            if (visited.find(neighbor) == visited.end())
            {
                if (DFSSearch(neighbor, targetNode, visited, path))
                {
                    return true;
                }
            }
        }

        path.pop_back();
        return false;
    }

    // 开始深度优先搜索
    void startDFS(char startNode, char targetNode)
    {
        unordered_set<char> visited;
        vector<char> path;
        cout << "DFS 搜索 " << startNode << " -> " << targetNode << ": ";
        if (!DFSSearch(startNode, targetNode, visited, path))
        {
            cout << "Path not found from " << startNode << " to " << targetNode << endl;
        }
    }

    // 所有路径的显示，并显示每个路径的边总数，同时指示边数量最长路径和边最短路径
    void allPathsUtil(char startNode, char endNode, vector<char> &path, unordered_set<string> &paths, unordered_map<string, int> &pathEdgeCount, int &minEdges, int &maxEdges)
    {
        path.push_back(startNode);
        if (startNode == endNode)
        {
            string edgePath;
            int edgeCount = path.size() - 1;
            for (int i = 0; i < path.size() - 1; ++i)
            {
                edgePath += "(" + string(1, path[i]) + ", " + string(1, path[i + 1]) + ") ";
            }
            paths.insert(edgePath);
            pathEdgeCount[edgePath] = edgeCount;
            minEdges=min(minEdges, edgeCount);
            maxEdges=max(maxEdges, edgeCount);
        }
        else
        {
            for (char neighbor : adjacencyList[startNode])
            {
                if (find(path.begin(), path.end(), neighbor) == path.end())
                {
                    allPathsUtil(neighbor, endNode, path, paths, pathEdgeCount,minEdges,maxEdges);
                }
            }
        }
        path.pop_back();
    }

    void displayAllPaths(char startNode, char endNode)
    {
        vector<char> path;
        unordered_set<string> paths;
        unordered_map<string, int> pathEdgeCount;
                int minEdges = INT_MAX;
        int maxEdges = INT_MIN;
        allPathsUtil(startNode, endNode, path, paths, pathEdgeCount,minEdges,maxEdges);

        cout << "所有路径" << startNode << " -> " << endNode << ":" << endl;
        for (const string &edgePath : paths)
        {
            cout << edgePath << " (边数: " << pathEdgeCount[edgePath] << ")" << endl;
        }
        cout << "边最长路径: " << minEdges << endl;
        cout << "边最短路径: " << maxEdges << endl;
    }
};
